// bitmap.c 
//	Routines to manage a bitmap -- an array of bits each of which
//	can be either on or off.  Represented as an array of integers.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "bitmap.h"
#include "system.h"

//----------------------------------------------------------------------
// BitMap::BitMap
// 	Initialize a bitmap with "nitems" bits, so that every bit is clear.
//	it can be added somewhere on a list.
//
//	"nitems" is the number of bits in the bitmap.
//----------------------------------------------------------------------

BitMap::BitMap(int nitems) 
{ 
    numBits = nitems;
    numWords = divRoundUp(numBits, BitsInWord);
    map = new unsigned int[numWords];
    for (int i = 0; i < numBits; i++) 
        Clear(i);
}

//----------------------------------------------------------------------
// BitMap::~BitMap
// 	De-allocate a bitmap.
//----------------------------------------------------------------------

BitMap::~BitMap()
{ 
    delete map;
}

//----------------------------------------------------------------------
// BitMap::Set
// 	Set the "nth" bit in a bitmap.
//
//	"which" is the number of the bit to be set.
//----------------------------------------------------------------------

void
BitMap::Mark(int which) 
{ 
    ASSERT(which >= 0 && which < numBits);
    map[which / BitsInWord] |= 1 << (which % BitsInWord);
}
    
//----------------------------------------------------------------------
// BitMap::Clear
// 	Clear the "nth" bit in a bitmap.
//
//	"which" is the number of the bit to be cleared.
//----------------------------------------------------------------------

void 
BitMap::Clear(int which) 
{
    ASSERT(which >= 0 && which < numBits);
    map[which / BitsInWord] &= ~(1 << (which % BitsInWord));
}

//----------------------------------------------------------------------
// BitMap::Test
// 	Return TRUE if the "nth" bit is set.
//
//	"which" is the number of the bit to be tested.
//----------------------------------------------------------------------

bool 
BitMap::Test(int which)
{
    ASSERT(which >= 0 && which < numBits);
    
    if (map[which / BitsInWord] & (1 << (which % BitsInWord)))
	return TRUE;
    else
	return FALSE;
}

//----------------------------------------------------------------------
// BitMap::Find
// 	Return the number of the first bit which is clear.
//	As a side effect, set the bit (mark it as in use).
//	(In other words, find and allocate a bit.)
//
//	If no bits are clear, return -1.
//----------------------------------------------------------------------

//added this --edit
int
BitMap::firstFit(int numPages)
{
            int openPages = 0, startPage = 0;
			int i;
			for(i = 0; i < numBits; i++)
			{
                if(Test(i))
                {
                        openPages = 0;
                        startPage = i;  //sets the variables to the restart the count of open pages
                                                                //let startPage start at the new number to see where the last on bit is
                }
                else
                {
                         openPages++;
                         if(openPages == numPages)
							 break;
                }
			}
            return startPage; //want the startpage to be invalid unless we have found a fit
}

int
BitMap::bestFit(int numPages)
{
        int openCount = 0, totPages = 0, check = 0;
        int startPage = 0;
		int i;
		for(i = 0; i < numBits; i++)
        {
			if(Test(i))
			{
                if(totPages == 0 && openCount >= numPages) //so this happens only once on the loop --edit
                   totPages = openCount; //saves the first value of the total number of open pages that were last found
                else if(totPages <= openCount && check == 0)  //uses the check variable to see if the values have already been checked
						totPages = openCount;  //saves the new value of total number of open pages that were found to best fit
				startPage = i; //This is storing the last bit that was one so we know where the open pages started
				check++;
                openCount = 0;
                
			}
			else
			{
                openCount++;				
                check = 0;
			}
		}
		
        return startPage;
}

int
BitMap::worstFit(int numPages)
{
        int openCount = 0, totPages = 0, check = 0;
        int startPage = 0;
		int i;
		for(i = 0; i < numBits; i++)
        {
			if(Test(i))
			{
                if(totPages == 0 && openCount >= numPages) //so this happens only once on the loop --edit
                   totPages = openCount; //saves the first value of the total number of open pages that were last found
                else if(totPages >= openCount && check == 0)  //uses the check variable to see if the values have already been checked
						totPages = openCount;  //saves the new value of total number of open pages that were found to best fit
				startPage = i; //This is storing the last bit that was one so we know where the open pages started
				check++;
                openCount = 0;
                
			}
			else
			{
                openCount++;				
                check = 0;
			}
		}
        return startPage;
}

//Searches the pages for open pages and keeps a count of how many are open in a specific space --edit
int
BitMap::Search(int numPages)
{
    int startPage = 0;	
    if(Task == 1)
	{
		startPage = firstFit(numPages); 
	}
	if(Task == 2)
	{
		startPage = bestFit(numPages);
	}
    if(Task == 3)
	{
		startPage = worstFit(numPages);
	}
	if(Task == 0)
	{
		startPage = firstFit(numPages);
	}
    return startPage; //startPage is returned after the search is complete to allocate memory --edit
}
//end of what I added --edit


//----------------------------------------------------------------------
// BitMap::Find
// 	Return the number of the first bit which is clear.
//	As a side effect, set the bit (mark it as in use).
//	(In other words, find and allocate a bit.)
//
//	If no bits are clear, return -1.
//----------------------------------------------------------------------
int 
BitMap::Find() 
{
    for (int i = 0; i < numBits; i++)
	if (!Test(i)) {
	    Mark(i);
	    return i;
	}
    return -1;
}

//----------------------------------------------------------------------
// BitMap::NumClear
// 	Return the number of clear bits in the bitmap.
//	(In other words, how many bits are unallocated?)
//----------------------------------------------------------------------

int 
BitMap::NumClear() 
{
    int count = 0;

    for (int i = 0; i < numBits; i++)
	if (!Test(i)) count++;
    return count;
}

//----------------------------------------------------------------------
// BitMap::Print
// 	Print the contents of the bitmap, for debugging.
//
//	Could be done in a number of ways, but we just print the #'s of
//	all the bits that are set in the bitmap.
//----------------------------------------------------------------------

void
BitMap::Print() 
{
    printf("Bitmap set:\n"); 
    for (int i = 0; i < numBits; i++)
	if (Test(i))
	    printf("%d, ", i);
    printf("\n"); 
}

// These aren't needed until the FILESYS assignment

//----------------------------------------------------------------------
// BitMap::FetchFromFile
// 	Initialize the contents of a bitmap from a Nachos file.
//
//	"file" is the place to read the bitmap from
//----------------------------------------------------------------------

void
BitMap::FetchFrom(OpenFile *file) 
{
    file->ReadAt((char *)map, numWords * sizeof(unsigned), 0);
}

//----------------------------------------------------------------------
// BitMap::WriteBack
// 	Store the contents of a bitmap to a Nachos file.
//
//	"file" is the place to write the bitmap to
//----------------------------------------------------------------------

void
BitMap::WriteBack(OpenFile *file)
{
   file->WriteAt((char *)map, numWords * sizeof(unsigned), 0);
}
